14.1 並列化するのに十分な仕事はあるのか？
並列化の目的
ハードウェア資源の利用率を上げる
時間的オーバーヘッドを削減
停止時間の短縮
ストップザワールドコレクション
コレクションサイクルの短縮
インクリメンタルコレクション
並行コレクション
並列化のための条件
並列化する価値が確かである
同期のためのコストを上回る利益を得られるだけの十分な量の仕事
並列化に適さない問題もある
リストをたどる操作は本質的に逐次的
並列マークフェーズにおいて$ p個のプロセッサがストールする回数$ n
$ n\le(p-1)\cdot\max_{o\in\mathit{reachable}}\mathit{depth}(o)
$ \mathit{reachable}: 到達可能なオブジェクトの集合
$ \mathit{depth}(o): ルートから$ oまでの最短経路の長さ
マークの各ステップにかかる時間が等しいと仮定
配列と普通のオブジェクトでは異なる
実際には並列化できる仕事はたくさんある
多様なデータ構造
木のように分岐を含むもの
複数の追跡の開始点
グローバル変数
ミューテータスレッドのスタック
リメンバードセット
潜在的並列性
多くのプログラムの深さの最大値はかなり浅い
Javaのベンチマークによる結果
マークされたオブジェクトの4%未満しかストールしない
潜在的並列性が高いことを示唆
32プロセッサまで増やしても良好にスケール
追跡処理に潜在する並列性は見つけにくい
他の並列化はより単純
スイープ
参照の付け替え
自明な並列化
プロセッサごとに担当する領域を分割
細部には悪魔が潜んでいる